#include <stdlib.h>

struct node {
  size_t id;
  void *ptr;
  size_t size;
  struct node *next;
};

struct allocator {
  void *base_addr;
  size_t mem_size;
  struct node *head;
} ma;

int ma_init(size_t mem) {
  ma.base_addr = malloc(mem);
  if (ma.base_addr == NULL)
    return 0;

  ma.mem_size = mem;
  ma.head = (struct node*)malloc(sizeof(struct node));
  if (ma.head == NULL)
    return 0;

  ma.head->id = 1;
  ma.head->ptr = ma.base_addr;
  ma.head->next = NULL;
  return 1;
}

size_t ma_alloc(size_t sz) {
  struct node *node = ma.head;
  while (node->next != NULL)
    node = node->next;

  if ((size_t)node->ptr + sz > (size_t)ma.base_addr + ma.mem_size)
    return 0;
  //printf("allocated from %u to %u\n", node->ptr, (size_t)node->ptr + sz);

  node->size = sz;
  node->next = (struct node*)malloc(sizeof(struct node));
  node->next->id = node->id + 1;
  node->next->ptr = (size_t)node->ptr + sz;
  node->next->next = NULL;

  return node->id;
}

void* ma_get(size_t id) {
  struct node *node = ma.head;
  while (node->next != NULL) {
    if (node->id == id)
      return node->ptr;
    node = node->next;
  }
  if (node->id != id)
    return NULL;
  return node->ptr;
}

int ma_free(size_t id) {
  struct node *prev_node = NULL, *next_node;
  struct node *node = ma.head;
  int success = 0;
  while (1) {
    if (node->id == id) {
      int flag = 0;
      size_t offset = node->size;
      next_node = node->next;
      if (prev_node != NULL) {
        prev_node->next = next_node;
        flag++;
      }

      if (next_node != NULL) {
        if (prev_node == NULL)
          ma.head = next_node;
        while (next_node->next != NULL) {
          memcpy((size_t)next_node->ptr - offset, next_node->ptr,
                 next_node->size);
          next_node->ptr = (size_t)next_node->ptr - offset;
          next_node = next_node->next;
        }
        memcpy((size_t)next_node->ptr - offset, next_node->ptr,
               next_node->size);
        next_node->ptr = (size_t)next_node->ptr - offset;
        flag++;
      }

      if (flag != 0)
        free(node);
      success = 1;
      break;
    }
    if (node->next == NULL)
      break;
    prev_node = node;
    node = node->next;
  }
  
  if (!success)
    return 0;
  return 1;
}

void ma_deinit() {
  struct node *node = ma.head, *tmp;
  while (node->next != NULL) {
    tmp = node;
    node = node->next;
    free(tmp);
  }
  free(node);
  free(ma.base_addr);
}

int main() {
  if (ma_init(2 * 1024 * 1024) == 0) {
    printf("Unable to initialize allocator\n");
    return 1;
  }
  size_t id_a, id_b, id_c;
  int *a, *c;
  char *b;

  id_a = ma_alloc(1024 * 1024);
  if (id_a == 0) {
    printf("Unable to allocate memory\n");
    return 1;
  }
  a = (int*)ma_get(id_a);
  printf("%u\n", a);
  a[0] = 1; a[1] = 0; a[2] = 15; a[3] = 2;
  if (ma_free(id_a) == 0) {
    printf("Unable to free memory\n");
  }

  id_b = ma_alloc(1024 * 1024);
  if (id_b == 0) {
    printf("Unable to allocate memory\n");
    return 1;
  }
  b = (char*)ma_get(id_b);
  printf("%u\n", b);
  b = "hello,world";

  id_c = ma_alloc(512 * 1024);
  if (id_c == 0) {
    printf("Unable to allocate memory\n");
    return 1;
  }
  c = (int*)ma_get(id_c);
  printf("%u\n", c);
  c[0] = -1; c[1] = 111;

  if (ma_free(id_b) == 0 || ma_free(id_c) == 0) {
    printf("Unable to free memory\n");
    return 1;
  }

  ma_deinit();
  return 0;
}

